/*
  Grupo 2
  
  Luiz Felipe de Souza Mattos 	RA 107822
  
  Debora Maia Silva 	      	RA 101985

*/

/* 
Programa que monta e insere em uma arvore B informacoes dos alunos (nome e RA), na ordem certa de busca.
Quando as paginas ficam cheias, promove a chave do meio para o nivel acima e quebra a pagina da insercao em
duas, conectando corretamente cada pagina na posicao certa.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arvoreb.h"

/* coloca o caracter '\0' em todas as posicoes do vetor string */
void limpa_string(char *string)
{
	int j;

	for (j = 0;j < 64;j++)
			string[j] = '\0';
}

/* libera a memoria usada pelas informacoes de ra e nome de uma pagina */
void libera_info(pagina *pag)
{
	free(pag->info);
}

/* libera a memoria usada pelo vetor de ponteiros da pagina */
void libera_ponteiros(pagina *pag)
{
	free(pag->ponteiros);
}

/* libera a memoria usada pela pagina */
void libera_pagina(pagina *pag)
{
	free(pag);
}

/* inicializa uma pagina, com -1 em todos os ras, limpa os nomes e atribui NULL aos ponteiros */
void inicializa(pagina *pag,int chaves)
{
	int i;

	for (i = 0;i < chaves;i++)
	{
		pag->info[i].ra = -1;
		limpa_string(pag->info[i].nome);
		pag->ponteiros[i] = NULL;
	}
	/* atribui NULL a ultima posicao do vetor de ponteiros, pois seu tamanho e uma
	casa maior do que o numero de chaver das paginas */
	pag->ponteiros[i] = NULL;
}

/* cria um no cabeca para a arvore B */
arvoreb * arvoreb_cria(int ordem)
{
	arvoreb *arvore;

	arvore = (arvoreb *)malloc(sizeof(arvoreb));
	arvore->chaves = (ordem * 2) - 1;
	arvore->raiz = NULL;

	return arvore;
}

/* aloca uma nova pagina na memoria e inicializa suas informacoes */
pagina * arvoreb_novapagina(int chaves)
{
	pagina *nova;
	
	nova = (pagina *)malloc(sizeof(pagina));
	nova->info = (aluno *)malloc(chaves * sizeof(aluno));
	nova->ponteiros = (pagina **)malloc((chaves + 1) * sizeof(pagina *));
	nova->pai = NULL;

	inicializa(nova,chaves);

	return nova;
}

/* quebra uma pagina em duas a partir da posicao passada e retorna a nova pagina criada */
pagina * arvoreb_quebra(int chaves,pagina *pag,int posicao)
{
	pagina *novo;
	int i,j = 0;
	
	novo = arvoreb_novapagina(chaves);

	novo->pai = pag->pai;
	
	i = posicao + 1;

	/* copia as chaves da pagina a ser quebrada para a pagina nova e 
	limpa as chaves correspondentes na pagina */
	while (i < chaves)
	{
		novo->info[j] = pag->info[i];
		pag->info[i].ra = -1;
		limpa_string(pag->info[i].nome);
		i++;
		j++;
	}
	
	/* copia os ponteiros da pagina para a pagina nova, atualizando o pai
	de cada filho da pagina */
	j = 0;
	for (i = posicao + 1;i <= chaves;i++)
	{
		novo->ponteiros[j] = pag->ponteiros[i];
		if (novo->ponteiros[j] != NULL)
			novo->ponteiros[j]->pai = novo;
		pag->ponteiros[i] = NULL;
		j++;
	}

	return novo;
}

/* busca na pagina passada, a posicao da chave na pagina ou onde deveria ficar */
int busca_posicao(pagina *pag,int ra,int chaves)
{
	int i = 0;

	while (pag->info[i].ra < ra && i < chaves && pag->info[i].ra != -1)
	{
		i++;
	}

	return i;
}

/* funcao recursiva que busca a posicao do ra na arvore caso ele ja tenha sido adicionado, e a posicao de onde 
o ra procurado deveria ficar na arvore, atualiza uma variavel atraves de um ponteiro para indicar a posicao
e retorna o ponteiro para a pagina onde o ra esta ou deveria estar */
pagina * arvoreb_busca(int chaves,pagina *pag,int ra,int *posicao)
{
	int posicaoaux;

	posicaoaux = busca_posicao(pag,ra,chaves);

	if (posicaoaux == chaves)
	{
		if (pag->ponteiros[posicaoaux] != NULL)
		{
			return arvoreb_busca(chaves,pag->ponteiros[posicaoaux],ra,posicao);
		}
		else
		{
			*posicao = posicaoaux;
			return pag;
		}
	}
	else
	{
		if (pag->info[posicaoaux].ra == ra)
		{
			*posicao = posicaoaux;
			return pag;
		}
		else
		{
			if (pag->ponteiros[posicaoaux] != NULL)
			{
				return arvoreb_busca(chaves,pag->ponteiros[posicaoaux],ra,posicao);
			}
			else
			{
				*posicao = posicaoaux;
				return pag;
			}
		}
	}
}

/* limpa as informacoes de uma posicao de uma chave passada como parametro */
void limpaChave (pagina *pag, aluno inf, int inicio, int chaves)
{
	int posicao;
	pagina *aux;
	
	aux = arvoreb_busca(chaves,pag, inf.ra,&posicao);
	
	pag->info[posicao].ra = -1;
	limpa_string(pag->info[posicao].nome);
	pag->ponteiros[posicao + 1] = NULL;
}

/* libera recursivamente as informacoes de nome e ra de todos os registros */
void limpa_info(pagina *pag,int chaves)
{
	int i = 0;

	if (i < chaves + 1)
	{
		while (pag->ponteiros[i] != NULL)
		{
			limpa_info(pag->ponteiros[i],chaves);
			i++;
		}
		libera_info(pag);
	}
	return;
}

/* insere a chave na pagina indicada, verificando se ha espaco ou se deve quebrar a pagina e promover
alguma chave para insercao */
void insereChaves(arvoreb **arv, pagina *pag, aluno inf, int posicao, /* numero de chaves */ int tamMax,pagina *insere)
{
	pagina  *novaPagina, *novaRaiz;
	aluno vetAux[tamMax]; /* auxiliar no deslocamento */
	pagina *vetPont[tamMax + 1];
	int i, posicaoAux, posicaoNova;
	int zero = 0,posicaopromove;
	aluno promove;
	
	if(pag->info[tamMax-1].ra != -1) /* se o ultimo tiver chave, ou seja, se a pagina estiver cheia */
	{
		promove = pag->info[tamMax / 2];
	
		novaPagina = arvoreb_quebra(tamMax, pag, tamMax / 2);

		/* insere a nova chave em pag ou novaPagina, dependendo se ela for maior ou menor do que
		a chave promovida. Cai na condicao de ter espacos vazios na pagina na proxima chamada recursiva */
		if (inf.ra < promove.ra)
		{
			posicaoAux = busca_posicao(pag,inf.ra,tamMax);
			/* caso seja um folha */
			if (pag->ponteiros[0] == NULL)
				/* nao precisa inserir o ponteiro para a pagina quebrada um nivel abaixo */
				insereChaves(arv,pag, inf, posicaoAux, tamMax,NULL);
			/* caso nao seja uma folha */
			else
				/* insere a chave, inserindo tambem o ponteiro para a pagina quebrada no nivel abaixo */
				insereChaves(arv,pag, inf, posicaoAux, tamMax,insere);
		}
		else
		{
			posicaoAux = busca_posicao(novaPagina,inf.ra,tamMax);
			/* caso seja um folha */
			if (novaPagina->ponteiros[0] == NULL)
				/* nao precisa inserir o ponteiro para a pagina quebrada um nivel abaixo */
				insereChaves(arv,novaPagina, inf, posicaoAux, tamMax,NULL);
			/* caso nao seja uma folha */
			else
				/* insere a chave, inserindo tambem o ponteiro para a pagina quebrada no nivel abaixo */
				insereChaves(arv,novaPagina, inf, posicaoAux, tamMax,insere);
		}
		
		/* busca a nova posicao da chave a ser promovida */
		posicaopromove = busca_posicao(pag,promove.ra,tamMax);
		
		/* Se o pai de pag for NULL, Cria nova raiz e atualiza ponteiros */
		if(pag->pai == NULL)
		{
			novaRaiz = arvoreb_novapagina(tamMax);
			
			insereChaves(arv,novaRaiz,promove , zero, tamMax,novaPagina); /* na nova raiz insere na posicao zero */
			
			/* atualiza ponteiro da posicaoPromove */
			novaRaiz->ponteiros[0] = pag;
			
			pag->pai = novaRaiz;
			novaPagina->pai = novaRaiz;

			/* atualiza a nova raiz da arvore */
			(*arv)->raiz = novaRaiz;
			
			/* limpa o retirado de novaPagina, atualiza a pagina */
			limpaChave(pag, promove, 0, tamMax);
		}
		
		/* Se o pai de paginaAux for diferente de NULL, Insere chave Promove no pai (nao insere na folha) */
		
		else if(pag->pai != NULL)
		{
			posicaoNova = busca_posicao(pag->pai,inf.ra,tamMax);
			insereChaves(arv,pag->pai, promove, posicaoNova, tamMax,novaPagina);
			limpaChave(pag, promove, 0, tamMax);
		}
	}
	
	else /* inserir em pagina que tem espaco */
	{
		if (pag->info[posicao].ra == -1) /* caso em que a posicao a ser inserida esta vazia */
		{
			limpa_string(pag->info[posicao].nome);
			pag->info[posicao] = inf;
			pag->ponteiros[posicao + 1] = insere;
			/* atualiza o pai da pagina quebrada na chamada recursiva anterior */
			if (insere != NULL)
				insere->pai = pag;
		}
		else /* tem que fazer o deslocamento */
		{
			/* copia para um vetor auxiliar as chaves e ponteiros a serem deslocados */
			for(i = posicao;i < tamMax;i++)
			{
				vetAux[i] = pag->info[i];
			}
			for(i = posicao + 1;i <= tamMax;i++)
			{
				vetPont[i] = pag->ponteiros[i];
			}
		
			/* insere a chave e o ponteiro correspondente */
			limpa_string(pag->info[posicao].nome);
			pag->info[posicao] = inf;
			pag->ponteiros[posicao + 1] = insere;
			/* atualiza o pai da pagina quebrada na chamada recursiva anterior */
			if (insere != NULL)
				insere->pai = pag;
		
			/* insere as chaves e ponteiros na pagina ja deslocados */
			for(i=posicao + 1;i < tamMax;i++)
			{
				pag->info[i] = vetAux[i - 1];
			}
			for(i=posicao + 2;i <= tamMax;i++)
			{
				pag->ponteiros[i] = vetPont[i - 1];
			}
		}
	}
}

/* insere as chaves novas na arvore, na posicao correta e promove as chaves caso seja necessario */
void arvoreb_insere(arvoreb **arv,aluno inf)
{
	int posicao;
	pagina *pag;

	if ((*arv)->raiz == NULL)
	{
		(*arv)->raiz = arvoreb_novapagina((*arv)->chaves);
		(*arv)->raiz->info[0].ra = inf.ra;
		strcpy((*arv)->raiz->info[0].nome,inf.nome);
		(*arv)->raiz->pai = NULL;
	}
	else
	{
		pag = arvoreb_busca((*arv)->chaves,(*arv)->raiz,inf.ra,&posicao);
	
		if (pag->info[posicao].ra == inf.ra)
		{
			return;
		}
		else
		{
			insereChaves(arv,pag,inf,posicao,(*arv)->chaves,NULL);
			return;
		}
	}
}

/* insere um elemento no final da lista ligada para ser impresso por largura */
void insere_lista(Lista *inicio,pagina *pag,int nivel)
{
	Lista *aux;
	
	aux = inicio;

	while (aux->prox != NULL)
		aux = aux->prox;

	aux->prox = (Lista *)malloc(sizeof(Lista));
	aux = aux->prox;
	aux->nivel = nivel;
	aux->pag = pag;
	aux->prox = NULL;
}

/* libera a lista temporaria usada na impressao */
void LiberaListaSimples(Lista **inicio)
{
	Lista *lixo,*aux;
	if (*inicio == NULL)
		return;	
	lixo = (*inicio);
	aux = lixo;
	while (lixo != NULL)
	{
		aux = aux->prox;
		free(lixo);
		lixo = aux;
	}
	*inicio = NULL;
	return;
}

/*imprime a arvore na ordem certa por largura */
void arvoreb_imprime_arv(arvoreb *arv)
{
	Lista *lista,*aux;
	int i = 0,nivel = 0;

	if (arv->raiz == NULL)
		return;

	/* inicializa a lista ligada */
	lista = (Lista *)malloc(sizeof(Lista));

	/* atribui a primeira pagina a lista ligada */
	lista->pag = arv->raiz;
	lista->prox = NULL;

	aux = lista;

	while (aux != NULL)
	{
		/* caso a pagina esteja em um nivel diferente na arvore, pula uma linha */
		if (aux->nivel == nivel + 1)
		{
			nivel++;
			printf("\n");
		}
		/* imprime todos os ras da pagina em ordem crescente */
		printf("{ ");
		for (i = 0;i < arv->chaves;i++)
		{
			if (aux->pag->info[i].ra != -1)
				printf("%d ",aux->pag->info[i].ra);
		}
		printf("}");
		/* insere por ordem da lista, os filhos de cada pagina em chaves de largura */
		for (i = 0;i < arv->chaves + 1;i++)
		{
			if (aux->pag->ponteiros[i] != NULL)
				insere_lista(lista,aux->pag->ponteiros[i],aux->nivel + 1);
		}
		/* atualiza o nivel atual */
		nivel = aux->nivel;
		aux = aux->prox;
	}
	printf("\n");
	LiberaListaSimples(&lista);
}

/* consulta a partir do ra o nome dos alunos */
void arvoreb_consulta(arvoreb *arv,int ra)
{
	int posicao;
	pagina *pag;

	if (arv->raiz == NULL)
		return;

	pag = arvoreb_busca(arv->chaves,arv->raiz,ra,&posicao);

	if (pag->info[posicao].ra == ra)
	{
		printf("%s",pag->info[posicao].nome);
	}

	return;
}

/* libera a memoria recursivamente de todas as paginas da arvore */
void destroi_paginas(pagina *pag,int chaves)
{
	int i = 0;

	if (i < chaves + 1)
	{
		while (pag->ponteiros[i] != NULL)
		{
			destroi_paginas(pag->ponteiros[i],chaves);
			i++;
		}
		libera_ponteiros(pag); 
		libera_pagina(pag);
	}
	return;
}

/* libera toda a memoria usada pela arvore B */
void arvoreb_destroi(arvoreb **arv)
{
	if ((*arv)->raiz != NULL)
	{
		limpa_info((*arv)->raiz,(*arv)->chaves);
		destroi_paginas((*arv)->raiz,(*arv)->chaves);
	}
	free(*arv);
}

